package contest.sweek204;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/8/30 10:28
 */
public class Solution4 {

    public int numOfWays(int[] nums) {
        return (int) ((dfs(nums, 0, nums.length - 1) - 1) % (long) 1000000007);
    }

    private long dfs(int[] nums, int l, int r) {
        if (r - l <= 1) return 1;
        int root = nums[l];
        int i = l + 1;
        for (; i <= r; i++) {
            if (nums[i] > root) break;
        }
        int len_l = i - l - 1;
        int len_r = r - i + 1;
        long left = dfs(nums, l + 1, i - 1);
        long right = dfs(nums, i, r);
        if (len_l == 0) return right;
        long cur = cal(len_l, r - l);
        return cur * left * right;
    }

    private long cal(long a, long b) {
        if (a == b) return 1;
        if (a == 1) return b;
        long s = b - a;
        long sum = 1;
        long mul = 1;
        for (long i = b; i > a; i--) {
            sum *= i;
        }
        for (long i = 1; i <= a; i++) {
            mul *= i;
        }
        return sum / mul;
    }
}
